The present invention relates to partial scan testing of sequential circuits and specifically to the resynthesis and retiming of the circuit to achieve partial scan testing with fewer scan flip-flops.
Partial scan testing of circuits has evolved as a prevalent design for testability technique for cost-effective sequential Automatic Test Generation methodology (ATPG). The cost associated with the partial scan methodology is related to the number of flip-flops (FFs) that are scanned. The goal of any partial scan approach is to select a minimum number of scan flip-flops such that sequential ATPG achieves high fault coverage. Empirical analysis of several circuits shows that the test generation complexity for sequential circuits grows exponentially with the length of the cycles in the FF dependency graph of the circuit. A FF dependency graph of a circuit captures the signal dependencies among the FFs. The graph has a vertex for every FF and there is an arc from vertex u to v whenever there is a combinational path from FF u to FF v.
An efficient partial scan approach is to select FFs in the minimum feedback vertex set (MFVS) of the FF dependency graph, so that all loops, except self-loops, are broken. While the conventional partial scan approaches consider the position of the FFs fixed, recent approaches investigate repositioning the FFs of the circuit by retiming before selecting the scan FFs. Retiming is a technique to re-position FFs in the sequential circuit without modifing the input-output behavior of the circuit. Several configurations of FFs can be obtained by retiming. It was proposed in an article by D. Kagaris and S. Tragoudas entitled "Partial Scan with Retirelug," in Proc. Design Automation Conference, pages 249-254, 1993, that a binary minimal state configuration (there is no more than one FF at the output of any gate) in which the number of FFs in the circuit is minimum, is the desired retirelug configuration to reduce the number of scan FFs needed to make the circuit acyclic. Techniques were suggested in the article to obtain the binary minimal state configuration from a given initial circuit.
It has been observed that most of the hard-to-detect faults in a sequential circuit occur in moderately sized or large strongly connected components of the circuit. Based on this observation, a retirelug approach was discovered previously by the inventors to improve the testability of the circuit by minimizing the number of FFs in the strongly connected components of the circuit. However, minimizing the number of FFs in the circuit, or minimizing the number of FFs in the strongly connected components of the circuit, may not be able to produce a circuit whose MFVS has the minimum cardinality of all the retiming configurations possible.
In order to understand the advantages of retiming, consider the sequential circuit shown in FIG. 1(a). The corresponding FF dependency graph is shown in FIG. 1(b). The MFVS of the FF dependency graph includes two FFs: either X and Y, or X and Z, or Y and Z. FFs in the MFVS can be scanned so that all cycles, except self-loops, are broken.
The circuit shown in FIG. 1(a) corresponds to a binary minimal state configuration. This is because there is at most one FF at the output of any gate, and the number of FFs in the circuit cannot be further minimized. Consequently, the retiming technique proposed in Kagaris et al cannot, further reduce the number of scan FFs needed to make the circuit acyclic. Also, the number of FFs in strongly connected components of the circuit cannot be further minimized. Consequently, the retiming approach previously proposed by the inventors is also not effective in reducing the size of the MFVS further.
A circuit graph has a vertex for every gate in the circuit and there is an arc between two vertices a and b if gate a drives gate b. The MFVS of the circuit graph is a list of gates whose removal makes the circuit or the circuit graph acyclic. The MFVS of a circuit is clearly a lower bound on the MFVS of the FF dependency graph of the circuit. Therefore, the circuit MFVS serves as a lower bound on the number of flip-flops that have to be selected for partial scan to break all cycles in the FF dependency graph. Referring to the circuit shown in FIG. 1(a), the circuit MFVS includes three gates c, d and e. If these gates are removed from the circuit, the modified circuit becomes acyclic. The corresponding FF dependency graph for the modified circuit also has no cycles. The gates d and e are chosen only to break cycles in the circuit that correspond to self-loops in the FF dependency graph of the circuit. Since high sequential test efficiency can be achieved even in the presence of self-loops, the circuit MFVS need only include gates that eliminate all cycles in the FF dependency graph, except self-loops. In the present invention, consideration is given only to breaking all cycles other than self-loops in the circuit or the FF dependency graph. As an example, consider again the circuit of FIG. 1(a). Including gate c in the circuit MFVS is sufficient to break all cycles in the FF dependency graph. The resultant circuit is shown in FIG. 1(c), and the corresponding FF dependency graph is shown in FIG. 1(d). Note that inclusion of gate c in the circuit MFVS results in eliminating the dependencies between FF and FFs Y, Z. Also, the dependency of FF Y on FF Z is eliminated. The FF dependency graph in FIG. 1(d) has no cycles, except self-loops. Gate c in FIG. 1(a) represents the Circuit Minimum Feedback Vertex Set (CMFVS), the minimum set of gates to be included in the MFVS to break all cycles in the circuit. If it is possible to achieve a circuit configuration in which every CMFVS gate drives a flip-flop, then these flip-flops can be selected for partial scan. Referring again to the circuit in FIG. 1(a), gate c does not drive a FF. Also, there does not exist a retimed configuration in which c drives a flip-flop. This is because FFs Y and Z cannot be moved backward to gate c due to the presence of the fanout from gate d to the primary output (PO), f. Similarly, the presence of the primary input (PI) i to gate b blocks the forward movement of the FFs Y and Z through gate b to the output of gate c.
However, in accordance with the teachings of the present invention, a combination of resynthesis and retiming can achieve the desired configuration. FIG. 1(e) shows the circuit after resynthesis, where gate d has been duplicated, so that there is no path to a PO blocking the backward movement of FFs to the desired location, gate c. The resynthesized circuit in FIG. 1(e) can now be retimed to obtain the desired retiming configuration shown in FIG. 1(f). Note the presence of FF P at the output of the CMFVS gate c. The corresponding FF dependency graph is shown in FIG. 1(g). Since c is the only CMFVS gate, the MFVS of the final circuit includes only one FF, P. Instead of having to scan two FFs in the original circuit in FIG. 1(a), scanning one FF is sufficient to break all cycles, in the resynthesized and retimed circuit shown in FIG. 1(f). The above example demonstrates the feasibility of transforming a circuit, by resynthesis and retiming, to produce a circuit with minimum-cardinality MFVS.